#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "dlist.h"

int listhead_init(dlist_t **li, int size)
{
	dlist_t *me = NULL;

	me = malloc(sizeof (dlist_t));
	if (NULL == me)
		return -1;
	me->size = size; // 每个数据元素的size
	me->node.next = &me->node;
	me->node.prev = &me->node;

	*li = me;

	return 0;
}

static node_t *__alloc_node(int size, const void *data)
{
	node_t *new_node;

	new_node = malloc(sizeof (node_t) + size);
	if (NULL == new_node)
		return NULL;
	
	memcpy(new_node->data, data, size);
	new_node->next = new_node;
	new_node->prev = new_node;

	return new_node;
}

int list_empty(const dlist_t *li)
{
	return li->node.next == &li->node && li->node.prev == &li->node;
}

static void __insert_node(node_t *p, node_t *n, node_t *node)
{
	node->prev = p;
	node->next = n;
	p->next = node;
	n->prev = node;
}

int list_insert_head(dlist_t *li, const void *data)
{
	node_t *n = __alloc_node(li->size, data);
	if (NULL == n)
		return -1;

	__insert_node(&li->node, li->node.next, n);

	return 0;
}

int list_insert_tail(dlist_t *li, const void *data)
{
	node_t *n = __alloc_node(li->size, data);
	if (NULL == n)
		return -1;
	
	__insert_node(li->node.prev, &li->node, n);

	return 0;
}

static node_t *__find_node(const dlist_t *li, const void *key, cmp_t cmp)
{
	node_t *cur = NULL;

	for (cur = li->node.next; cur != &li->node; cur = cur->next) {
		if (0 == cmp(cur->data, key))
			return cur;
	}

	return NULL;
}

void *list_find(const dlist_t *li, const void *key, cmp_t cmp)
{
	node_t *cur;

	cur = __find_node(li, key, cmp);
	if (NULL == cur)
		return NULL;
	return cur->data;
}

static void __delete(node_t **d)
{
	(*d)->prev->next = (*d)->next;
	(*d)->next->prev = (*d)->prev;
	(*d)->prev = (*d)->next = *d;

	free(*d);
	(*d) = NULL;
}

int list_delete(dlist_t *li, const void *key, cmp_t cmp)
{
	node_t *del;

	del = __find_node(li, key, cmp);
	if (NULL == del)
		return -1;

	__delete(&del);

	return 0;
}

int list_fetch(dlist_t *li, const void *key, cmp_t cmp, void *data)
{
	node_t *del;

	del = __find_node(li, key, cmp);
	if (NULL == del)
		return -1;

	memcpy(data, del->data, li->size);

	__delete(&del);

	return 0;
}

void list_travel(const dlist_t *li, pri_t pri)
{
	node_t *cur = NULL;

	for (cur = li->node.next; cur != &li->node; cur = cur->next) {
		pri(cur->data);

		printf("%16p%16p%16p\n", cur, cur->prev, cur->next);
	}
}

// 始终返回0,即始终判定相等
static int __always_cmp(const void *data, const void *key)
{
	return 0;
}

void list_destroy(dlist_t **li)
{
	while (!list_empty(*li)) {
		list_delete(*li, NULL, __always_cmp);
	}
	free(*li);
	*li = NULL;
}

// Extra

void *list_middle(dlist_t *li)
{
	node_t* fast = li->node.next; // 每次走两步
	node_t* slow = li->node.next; // 每次走一步

	while (fast != &li->node) {
		fast = fast->next;
		if (fast != &li->node) {
			// 还没走到头，再走一步
			fast = fast->next;
			// 要是fast没走到头slow再继续走，走到头的话slow就别走了
			slow = slow->next;
		}
	}

	return slow;
}

void list_reverse(dlist_t *li)
{
	node_t *p = &li->node;
	node_t *n;
	node_t *cur = li->node.next;
	
	// 交换头节点里的首尾指针
	n = li->node.prev;
	li->node.prev = li->node.next;
	li->node.next = n;

	// 遍历每一个节点调整其中指针
	while (cur != &li->node) {
		n = cur->next;
		cur->next = p;
		cur->prev = n;
		p = cur;
		cur = n;
	}
}

